#include <algorithm>
#include <functional>
#include <queue>

#include "tools.cpp"

class MedianFinder_simple {
  public:
    /** initialize your data structure here. */
    MedianFinder_simple() {}

    void addNum(int num) { datas.push_back(num); }

    double findMedian() {
        std::sort(datas.begin(), datas.end());
        if (datas.size() % 2 == 0) return (datas[datas.size() / 2] + datas[datas.size() / 2 - 1]) / 2.0;
        return datas[datas.size() / 2];
    }

  private:
    std::vector<int> datas;
};

class MedianFinder_binsearch {
  public:
    /** initialize your data structure here. */
    MedianFinder_binsearch() {}

    void addNum(int num) {
        datas.insert(datas.begin() + binary_search(num), num);
        print(datas);
        median = INT_MIN;
    }

    double findMedian() {
        if (median != INT_MIN) return median;
        if (datas.size() % 2 == 0)
            median = (datas[datas.size() / 2] + datas[datas.size() / 2 - 1]) / 2.0;
        else
            median = datas[datas.size() / 2];
        return median;
    }

    size_t binary_search(int num) {
        int low = 0, high = datas.size() - 1;
        while (high >= low) {
            int mid = (low + high) / 2;
            if (num > datas[mid]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

  private:
    std::vector<int> datas;
    double median;
};

class MedianFinder {
  public:
    void addNum(int num) {
        big_heap.push(num);
        // make the more big nums always in small_heap
        small_heap.push(big_heap.top());
        big_heap.pop();

        // balance the size, big_heap.size() - small_heap.size() == 1 or 0
        while (big_heap.size() < small_heap.size()) {
            big_heap.push(small_heap.top());
            small_heap.pop();
        }
    }

    int FindMedian() {
        if (big_heap.size() == small_heap.size()) return (big_heap.top() + small_heap.top()) * 0.5;
        return big_heap.top();
    }

  private:
    std::priority_queue<int> big_heap;
    std::priority_queue<int, std::vector<int>, std::greater<int>> small_heap;
};

int main() {
    MedianFinder me;
    me.addNum(1);
    me.addNum(2);
    me.addNum(3);
    me.addNum(2);
    me.addNum(2);
    me.addNum(8);
    me.addNum(2);
    me.addNum(9);
    me.addNum(2);
}
